package 代码随想录.链表.链表相交;

import java.util.HashSet;

public class Main {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        //求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        while (curA != null) {
            lenA++;
            curA=curA.next;
        }
        while(curB!=null){
            lenB++;
            curB=curB.next;
        }
        curA=headA;
        curB=headB;
        if(lenA<lenB){  //让curA为最长链表的头指针
            int temp=lenA;
            lenA=lenB;
            lenB=temp;
            ListNode tempNode=curA;
            curA=curB;
            curB=tempNode;
        }
        int gap=lenA-lenB;
        while(gap>0){
            curA=curA.next;
            gap--;
        }
        //此时两个位于同一起点，遍历两个链表，遇到相同直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    //哈希集合，将链表A的每个结点都加入哈希集合中，然后遍历链表B，并判断是否存在于哈希集合中
    //如果不在，则继续遍历B的下一个结点
    //如果存在，则B后面的结点都在哈希结合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB\textit{headB}headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode p = headA;
        while (p != null) {
            set.add(p);
            p = p.next;
        }
        p = headB;
        while (p != null) {
            if (set.contains(p)) {
                return p;
            } else {
                p = p.next;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node11 = new ListNode(10);
        ListNode node21 = new ListNode(9);
        node11.next = node21;
        node21.next = node3;

//        ListNode intersectionNode = getIntersectionNode(node1, node11);
        ListNode intersectionNode = getIntersectionNode1(node1, node11);
        assert intersectionNode != null;
        System.out.println(intersectionNode.val);
    }
}
class ListNode {
    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
